#ifndef SINGLELIST_H
#define SINGLELIST_H
#include <iostream>
using namespace std;

class SingleList
{
    public:
        SingleList(){
            head = new Node();
            len = 0;
        }
        ~SingleList(){
            head = nullptr;
        }
        class Node{
        public:
            Node(){
            }
            ~Node(){
                next = nullptr;
            }
            Node(int data):data(data){
            }
            int data;
            Node* next = nullptr;
        };

        int getLen(){
            return len;
        }
        SingleList::Node* getHead()const{
            return this->head;
        }
        void traverse(){
            SingleList::Node* p = this->head->next;
            cout<<"traverse SingleList[";

            while(p != nullptr){
                cout<<p->data<<" ";
                p = p->next;
            }
            cout<<"]\n";
        }
        // 0--head   len-last
        void addHead(int data){
            insert(data,0);
        }
        void addLast(int data){
            insert(data,this->len);
        }
        //插入index可以为len  因为len是待插入，没有数据的
        //插入是往index后插入
        void insert(int data, int index){
            if(!(index >=0 && index <= this->len)){
                cout<<"err index "<<index<<endl;
                return;
            }
            SingleList::Node* pre = findPreByIndex(index);
            if(pre == nullptr){
                return;
            }
            SingleList::Node* newNode = new Node(data);
            newNode->next = pre->next;
            pre->next = newNode;
            ++len;
        }
        int delHead(){
            return del(0);
        }
        int delLast(){
            return del(this->len-1);
        }
        //删除index!=len 因为len是待插入，没有数据的
        int del(int index){
            if(!(index >=0 && index < this->len)){
                cout<<"err index "<<index<<endl;
                return -1;
            }
            SingleList::Node* pre = findPreByIndex(index);
            if(pre == nullptr){
                return -1;
            }
            int data = pre->next->data;
            pre->next = pre->next->next;
            --this->len;
            return data;
        }

        SingleList* mergeList(SingleList &list, bool desc){
            SingleList* mList = new SingleList();
            SingleList::Node* thisN = this->head->next;
            SingleList::Node* tN = list.getHead()->next;
            bool hasNotNext  = (thisN == nullptr || tN == nullptr);
            while(!hasNotNext){
                if(desc){
                    if(thisN->data > tN->data){
                        mList->addLast(thisN->data);
                        thisN = thisN->next;
                    }else{
                        mList->addLast(tN->data);
                        tN = tN->next;
                    }
                }else{
                    if(thisN->data < tN->data){
                        mList->addLast(thisN->data);
                        thisN = thisN->next;
                    }else{
                        mList->addLast(tN->data);
                        tN = tN->next;
                    }
                }
                hasNotNext = (thisN == nullptr || tN == nullptr);
            }

            SingleList::Node* lp = thisN == nullptr ? tN : thisN;
            while(lp != nullptr){
                mList->addLast(lp->data);
                lp = lp->next;
            }
            return mList;
        }



    private:
        //返回index-1   不检查index
        SingleList::Node* findPreByIndex(int index){
            SingleList::Node *pre = head;
            //index从0开始     node[len] 是没有的
            //index=0, pre=head 把data插到node[0]
            //index=1, pre=node[0] 把data插到node[1]
            //index=len, pre=node[len-1] 把data插到node[len]
            for(int i=0; pre != nullptr && i<index; i++){
                pre = pre->next;
            }
            return pre;
        }


        Node* head;
        int len;
};

#endif // SINGLELIST_H